#include "link_list.h"
#include <stdio.h>
#include <string.h>

Status linklist_init(link_list *ll)
{
	*ll = (link_list) malloc(sizeof(lnode));
	if( !(*ll) ) exit(OVERFLOW);
	
	(*ll)->next = NULL;
	
	return SUCCESS;
}

Status linklist_destroy(link_list *ll)
{
	lnode *q, *p = (*ll)->next;
	while (p){
		q = p->next;
		free(p->data);
		free(p);
		p = q;
	}
	free(*ll);
	return SUCCESS;
}

Status linklist_clear(link_list ll)
{
	lnode *q, *p = ll->next;
	while (p){
		q = p->next;
		free(p->data);
		free(p);
		p = q;
	}
	ll->next = NULL;
	return SUCCESS;
}

size_t linklist_length(link_list ll)
{
	size_t i = 0;
	lnode *p = ll;
	while(p->next){
		i++;
		p = p->next;
	}
	return i;
}

void *linklist_getelem(link_list ll, size_t i)
{
	lnode *p = ll->next;
	while(--i && p) p = p->next;
	if(!p || i < 0) exit(ERROR);
	return p->data;
}

size_t linklist_locateelem(link_list ll, const void *e, 
		int cmp(const void *e1, const void *e2), 
		size_t struct_size)
{
	lnode *p = ll;
	size_t i = 1;
	while(p = p->next){
		if(cmp(p->data,e) == 0) 
			return i;
		i++;
	}
	return 0;
}

Status linklist_insert(link_list ll, size_t i, const void *e,
		size_t struct_size)
{
	lnode *p = ll,*ne;

	ne = (lnode *) malloc(sizeof(lnode));
	if(!ne) exit(OVERFLOW);
	ne->data = malloc(struct_size);
	if(!ne->data) exit(OVERFLOW);
	memcpy(ne->data, e, struct_size);

	while(--i && p) p = p->next;
	if(!p) return ERROR;

	ne->next = p->next;
	p->next = ne;

	return SUCCESS;
}

Status linklist_delete(link_list ll, size_t i, void *e, 
		size_t struct_size)
{
	lnode *p = ll, *q;
	while(--i && p->next) p = p->next;
	
	if(!p->next) return ERROR;
	
	memcpy(e, p->next->data, struct_size);
	q = p->next->next;
	free(p->next->data);
	free(p->next);
	p->next = q;
	
	return SUCCESS;
}
void linklist_traverse(link_list ll, Bool visit(const void *))
{
	lnode *p = ll;
	while(p = p->next)
		if(!visit(p->data))
			exit(ERROR);
}

/*
 * la,lb is non_increamental link list,
 * lc use la's head node, and we don't copy the data,
 * that is la and lb will be modified or free
 */
void linklist_merge(link_list *la, link_list *lb, link_list *lc, int compare(const void *, const void*))
{
	lnode *pa,*pb,*pc;
	pa = (*la)->next;
	pb = (*lb)->next;
	pc = (*lc) = (*la);
	while(pa && pb){
		if(compare(pa->data,pb->data) < 0){
			pc = pc->next = pa;
			pa = pa->next;
		}else{
			pc = pc->next = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;
	free(*lb);
}
